#include <cstdio>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/*
 * @lc app=leetcode.cn id=147 lang=cpp
 *
 * [147] 对链表进行插入排序
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode node(-5005); node.next = head;
        ListNode *pre = &node, *cur = head;
        while (cur) {
            if (pre->val > cur->val) {
                ListNode *pp = &node, *current = node.next;
                while (cur->val > current->val) { pp = current; current = current->next;}
                pre->next = cur->next;
                pp->next = cur; cur->next = current;
                cur = pre;
            }
            pre = cur; cur = cur->next;
        }
        return node.next;
    }
};
// @lc code=end

